package com.kk.algorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/*
 * @Description:    贪心算法 -- 实现广播问题
 * @Author:         阿K
 * @CreateDate:     2021/2/7 16:30
 * @Param:
 * @Return:
**/
public class GreedyAlgorithm {
    public static void main(String[] args) {
        // 创建用于存放所有广播电台的 map
        HashMap<String, HashSet<String>> broadcasts = new HashMap<> ( );

        //将各个电台放入到broadcasts
        HashSet<String> hashSet1 = new HashSet<> ( );
        hashSet1.add ("北京");
        hashSet1.add ("上海");
        hashSet1.add ("天津");
        HashSet<String> hashSet2 = new HashSet<> ( );
        hashSet2.add ("广州");
        hashSet2.add ("北京");
        hashSet2.add ("深圳");
        HashSet<String> hashSet3 = new HashSet<> ( );
        hashSet3.add ("成都");
        hashSet3.add ("上海");
        hashSet3.add ("杭州");
        HashSet<String> hashSet4 = new HashSet<> ( );
        hashSet4.add ("上海");
        hashSet4.add ("天津");
        HashSet<String> hashSet5 = new HashSet<> ( );
        hashSet5.add ("杭州");
        hashSet5.add ("大连");
        //加入到map
        broadcasts.put ("K1", hashSet1);
        broadcasts.put ("K2", hashSet2);
        broadcasts.put ("K3", hashSet3);
        broadcasts.put ("K4", hashSet4);
        broadcasts.put ("K5", hashSet5);

        //allAreas 存放所有的地区
        HashSet<String> allAreas = obtainAllAreas (broadcasts);

        //创建ArrayList, 存放选择的电台集合(最终答案)
        ArrayList<String> selects = new ArrayList<> ( );

        //定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<> ( );// 可以理解为不断变动的 allAreas

        // 定义maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
        // 若 maxKey 不为null ,则会加入到 selects
        String maxKey = null;

        while (allAreas.size ( ) != 0) {// 若 allAreas 不为 0，则表示还没有覆盖到所有地区（既没有全部剔除完）

            // maxKey 每次重新指向，都需要重置一次
            maxKey = null;

            // 遍历 broadcasts, 取出对应key
            for (String key : broadcasts.keySet ( )) {
                // 每次操作前 清空一次辅助集合
                tempSet.clear ( );
                // 当前 key(广播台)，所能覆盖的地区
                HashSet<String> areas = broadcasts.get (key);
                // 拷贝到 辅助集合
                tempSet.addAll (areas);
                // 求出 tempSet 和 allAreas 的交集，并赋值于 tempSet
                tempSet.retainAll (allAreas);
                // 若当前这个集合（广播台），包含的未覆盖地区的数量，比maxKey指向的集合地区还要多
                // 则需要重置 maxKey
                // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
                if (tempSet.size ( ) > 0 && (maxKey == null || tempSet.size ( ) > broadcasts.get (maxKey).size ( ))) {
                    maxKey = key;
                }
            }

            // maxKey != null, 就应该将maxKey 加入selects
            if (maxKey != null) {
                selects.add (maxKey);
                // 将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉(剔除)
                allAreas.removeAll (broadcasts.get (maxKey));
            }
        }

        System.out.println ("得到的选择结果是" + selects);//[K1,K2,K3,K5]
    }

    // 获取所有广播电台地区
    private static HashSet<String> obtainAllAreas(HashMap<String, HashSet<String>> broadcasts) {
        if (broadcasts != null && broadcasts.size ( ) > 0) {

            HashSet<String> allAreas = new HashSet<> ( );
            Set<String> keys = broadcasts.keySet ( );
            for (String key : keys) {
                HashSet<String> all = broadcasts.get (key);
                for (String region : all) {
                    // 因 HashSet 会覆盖，所以无需判断
                    allAreas.add (region);
                }
            }
            return allAreas;
        }
        return null;
    }
}
